Scheduling processing resources in a time-sharing system is one of the most critical tasks for any multi-resource operating system. A resource scheduler may apportion central processing unit (CPU) time to runnable resources in small time intervals, according to a scheduling policy. Since the scheduler runs for example every time interval, it may need to run efficiently regardless of the number of processes or processors in the system. Proportional sharing, or fair-share scheduling, is a scheduling policy that may allocate CPU time to each resources in a multi-resource system that is proportion to its assigned weight.
A multi-resource system may for example, contain M resources. If there are for example N tasks sharing the M resources, each task may be assigned a priority that may determine an order in which the task is given access to each resource. Furthermore, each task may be assigned a weight, for example, based on the quality of service requirement information associated with the task. The weight assigned to the task may for example, correspond to the length of time the task may use a resource relative to other tasks. For example, if two tasks have weights 1 and 3, then the ratio of the time that each task uses the shared resources may be 1 to 3. Ideally, a proportional-share scheduler may ensure that, during any time interval, each task may use each appropriate resource for a length of time proportional to the task's weight. Such a guarantee may require that, as the number of tasks grows, for a time interval, the tasks may be scheduled with infinitesimally small intervals of time. In practice, no an algorithm may achieve this guarantee for all possible time intervals.
However, a multi-resource scheduling mechanism that better approximates the ideal scheduler is desirable.
It will be appreciated that for simplicity and clarity of illustration, elements shown in the drawings have not necessarily been drawn accurately or to scale. For example, the dimensions of some of the elements may be exaggerated relative to other elements for clarity or several physical components included in one functional block or element. Further, where considered appropriate, reference numerals may be repeated among the drawings to indicate corresponding or analogous elements. Moreover, some of the blocks depicted in the drawings may be combined into a single function.